package com.peng.old.sort;


import com.peng.old.util.SortUtil;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 1, 8, 9, 20, 24, 7, 3, 2};
        int[] ints = SortUtil.makeRandomArray(1000);
        long l = System.currentTimeMillis();
        test1(ints);
        System.out.println(System.currentTimeMillis()-l);
        l = System.currentTimeMillis();
        test2(ints);
        System.out.println(System.currentTimeMillis()-l);
        System.out.println(SortUtil.checkResult(ints));

    }

    public static void test1(int[] arr) {
        //按数组一半长度进行分组，然后再取半直到1
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k >= i; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        SortUtil.swap(arr, k, k - i);
                    }
                }

            }

        }

    }


    public static void test2(int[] arr) {
        //Knuth序列
        int h = 1;
        while (h < arr.length / 3) {
            h = h * 3 + 1;
        }
        //按Knuth序列计算出的数值进行分组，然后再复原到1
        for (int i = h; i > 0; i = (i-1)/3) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k >= i; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        SortUtil.swap(arr, k, k - i);
                    }
                }

            }

        }

    }
}
